`
https://leetcode.cn/problems/course-schedule/
`

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  // 将依赖关系转换为图结构
  const graph = buildGraph(numCourses, prerequisites)

  // 构建入度数组
  const indegree = new Array(numCourses).fill(0)
  for (const edge of prerequisites) {
    const to = edge[0]
    indegree[to]++
  }

  // 构建队列，把入度为 0 的节点都作为遍历起始点
  const q = []
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) {
      q.push(i)
    }
  }

  // 记录遍历节点的个数
  let count = 0

  while (q.length) {
    // 弹出节点 cur，并将它指向的节点的入度减一
    const cur = q.shift()
    count++
    for (const next of graph[cur]) {
      indegree[next]--
      if (indegree[next] === 0) {
        // 如果入度变为 0，说明 next 依赖的节点都已被遍历
        q.push(next)
      }
    }
  }

  // 如果所有节点都被遍历过，说明不成环
  return count === numCourses
};

function buildGraph(numCourses, prerequisites) {
  const graph = new Array(numCourses).fill(null).map(() => [])
  for (const edge of prerequisites) {
    const from = edge[1], to = edge[0]
    graph[from].push(to)
  }
  return graph
}

// test
console.log(canFinish(2, [[1, 0]])) // true
console.log(canFinish(2, [[1, 0], [0, 1]])) // false
console.log(canFinish(3, [[1, 0], [1, 2], [0, 1]])) // false